/*************************************************************************
 * File Name:    Spiral_Matrix_II.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/17 23:04:38
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Probelm: Spiral Matrix II
 |
 | Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
 |
 | For example,
 | Given n = 3,
 |
 | You should return the following matrix:
 | [
 |   [ 1, 2, 3 ],
 |   [ 8, 9, 4 ],
 |   [ 7, 6, 5 ]
 | ]
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
public:
    vector<vector<int> > generateMatrix(int n)
    {
        vector<vector<int> > matrix(n, vector<int>(n, 0));
        
        int num = 0;
        for (int i = 0; i < n / 2; ++i) {
            for (int j = i; j < n - i; ++j) matrix[i][j] = ++num;
            for (int j = i + 1; j < n - i - 1; ++j) matrix[j][n - i - 1] = ++num;
            for (int j = n - i - 1; j >= i; --j) matrix[n - i - 1][j] = ++num;
            for (int j = n - i - 2; j >= i + 1; --j) matrix[j][i] = ++num;;
        }
        if (n & 1) matrix[n / 2][n / 2] = ++num;
        return matrix;
    }
};

